package offer.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author DengYuan2
 * @create 2021-02-25 19:31
 */
public class n_7 {
    public static void main(String[] args) {
        n_7 n = new n_7();
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        t1.left = t2;
        t1.right = t5;
        t2.left = t3;
        t2.right = t4;
        t5.left = t6;
        t5.right = t7;
        n.preOrder(t1);
        System.out.println();
        n.inOrder(t1);
        System.out.println();
        n.postOrder(t1);
        System.out.println();
        n.layerOrder(t1);
        System.out.println();
        int[] pre={1,2,3,4,5,6,7};
        int[] in = {3,2,4,1,6,5,7};
        TreeNode treeNode = n.reConstructBinaryTree2(pre, in);
        n.layerOrder(treeNode);
    }


    /**
     *
     * @param pre
     * @param in
     * @return
     */
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++) {
            map.put(in[i],i);
        }
        return helper(pre,0,pre.length-1,0);
    }

    public TreeNode helper(int[] array, int l,int r,int x) {
        if (l>r){
            return null;
        }
        TreeNode root = new TreeNode(array[l]);
        int idx = map.get(array[l]);
        int leftSize=idx-x;
        root.left=helper(array,l+1,l+leftSize,x);
        root.right=helper(array,l+leftSize+1,r,x+leftSize+1);
        return root;
    }


    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }

    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }

    /**
     * 层次遍历
     *
     * @param node
     */
    public void layerOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        TreeNode tmp = null;
        while (!queue.isEmpty()) {
            count = queue.size();
            for (int i = 0; i < count; i++) {
                tmp = queue.poll();
                System.out.print(tmp.val + " ");
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                    count++;
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                    count++;
                }
            }
        }
    }

    public TreeNode reConstructBinaryTree2(int [] pre,int [] in) {
        if (pre==null || in==null){
            return null;
        }
        TreeNode result = getResult(pre,0,pre.length-1,0);
        return result;
    }

    private TreeNode getResult(int[] pre, int start, int end, int inL) {
        if (start<end){
            return null;
        }
        int cur=pre[start];
        Integer idx = map.get(cur);
        TreeNode root = new TreeNode(cur);
        int leftSize=idx-inL;
        root.left=getResult(pre,start+1,start+leftSize,inL);
        root.right=getResult(pre,start+leftSize+1,end,inL+leftSize+1);
        return root;
    }


}
